In digital phase amplitude modulation, the modulated signal consists of a sequence of symbols in each of which a carrier has a selected phase and amplitude. Only certain phase/amplitude combinations are permitted; these combinations may be plotted on a diagram with in-phase and quadrature axes to form a pattern; the set of allowable points in this pattern is commonly referred to as a constellation. If for example, one has a 16 point constellation, it is a simple matter to modulate the signal with a 4-bit word to be transmitted by regarding each point as associated with a respective one of the 16 possible combinations of four bits.
It has been shown however that by using a larger constellation (e.g. 32 points) and a suitable coding of the 4 bits, the resultant inherent redundancy in the modulated symbol sequence can be exploited by a soft decision decoder to improve the reliability of decoding in the presence of noise to an extent which exceeds the degradation caused by the larger numbers of points and results in a net coding gain. Coding gain is defined as the difference (in dB) between the signal-to-noise ratio that a coded scheme needs to operate at a particular error rate and that needed by the equivalent uncoded system.
One method of achieving coding gain is by the use of convolutional coding; here however we are concerned primarily with block coding, though the synchronization arrangements to be described are not limited to such cases.
It is inherent in block coding that output symbols are generated on a block by block basis. Thus if a 16-point constellation is to be used for modulation at a rate of 3 bits/symbol, then the coding process needs to produce 4n bits (for selecting points in the constellation) for every 3n data bits received (where n is the length of a block of symbols).
Consider now the concept of set partitioning: the signal constellation is progressively partitioned into subsets having increasing minimum Euclidean distance between the points of each subset; .DELTA..sub.0 &lt;.DELTA..sub.1 &lt;.DELTA..sub.2 . . . as illustrated in FIG. 1 for 16 point quadrature amplitude modulation. The Euclidean distance is simply the linear distance on the phase diagram between adjacent points of a subset; thus, assuming the sixteen points are on a unit grid, ##EQU1##
This distance is significant in that it is a measure of the capability of a hard decision decoder to discriminate between points in the subset in the presence of noise. By labelling each partition with a binary digit as shown we form a partition tree. In FIG. 1 the label for each point is constructed from the bits labelling the partitions needed to reach it; it is convenient to write the bit corresponding to the first partition level as the rightmost bit of the point label and so on. We then see that points whose labels first differ (when read from right to left) in the ith position (where the rightmost bit is the first position) are a Euclidean distance of at least .DELTA..sub.i-1 apart.
The concept of set partitioning in this manner is discussed in G. Ungerboeck's paper "Channel coding with multilevel/phase signals", IEEE Trans IT-28, pp 55-67, January 1982.
The other primary consideration in the coding process is the Hamming distance of the code or codes employed. FIG. 2 illustrates the coding process, in the form of an array. Of a total of .SIGMA.k.sub.i input bits, k.sub.1 bits are coded by means of an (N, k.sub.1, d.sub.1) code to form a first row of bits a.sub.11 . . . a.sub.1N, k.sub.2 bits are coded by means of an (N, k.sub.2, d.sub.2) code to form the second row of bits a.sub.21 . . . a.sub.2N, and so on. The array has N columns, the bits of each column forming a point label L.sub.1 . . . L.sub.N.
An (n, k, d) code is one in which k input bits are coded into n bits, with a minimum Hamming distance of d.
For the 16 point constellation of FIG. 1 one might choose codes as set out below, with a block size of 8 symbols.
______________________________________ i code Euclidean Distance d.sub.i .DELTA..sup.2.sub.i-1.sup.2 ______________________________________ 1 (8, 1, 8) 1 8 2 (8, 4, 4) 2 8 3 (8, 7, 2) 4 8 4 (8, 8, 1) 8 8 ______________________________________
Total number of input bits=.SIGMA.k.sub.i =20.
The square Euclidean distance .DELTA..sup.2.sub.i-1 increases down the column, with the Hamming distance d decreasing down the column. The minimum value of the product d.sub.i .DELTA..sup.2.sub.i-1 is preferably large for good performance. Note that although the fourth row is actually uncoded--i.e. the 8 bits are simply 8 of the input bits unaltered, it is convenient to view this as an (n, n, 1) "code".
The codeword array concept is described in Imai & Hirakawa's paper "A new multilevel coding method using error-correcting codes", IEEE Trans IT-23, pp 371-377, May 1977, and in relation to Reed-Muller codes by E. Cusack, "Error control codes for QAM signalling", Elec. Letts., 20, pp 62-63, Jan. 19th 1984.
It is worth noting at this point that the labelling of bits in FIG. 1 is entirely systematic. Although in most cases this is the most convenient way of proceeding, it is not essential in all cases. In particular, if two rows of the array are coded with codes having the same Hamming distance (or are uncoded) then the lower of these two rows can be allowed a larger Euclidean distance without reducing the coding gain, and therefore the meaning of the two bits from these rows for any one or more symbols can be transposed with no effect, for example, if the bottom two rows are uncoded, then the allocation of the corresponding label bits to the signal points of the constellation can be entirely arbitrary (although this allocation may be subject to other constraints; e.g. for the purpose of achieving 90.degree. phase jump immunity, as will be discussed below). A departure from structured partitioning which results in a reduction of the minimum d.sub.i .DELTA..sup.2.sub.i-1 product will produce a degradation of performance but may still provide a performance better than that of the uncoded case. Indeed, random labelling does not necessarily preclude some coding gain, but for good results then, if we define the Euclidean significance of a label bit as being the smallest change of Euclidean distance that changing that bit can produce, it is preferable that the label bits do not all have the same Euclidean significance. In the following description, the term "significance" is used to mean Euclidean significance as defined above, and labels are written with the significances of the bits increasing from right to left (analogously to the conventional representation of binary numbers). This convention can give rise to ambiguity in that two bits of a given label can have the same significance, but no confusion arises since in this situation it generally does not matter which bit is which.
A modification to this method has been proposed by RGC Williams and PG Farrell in "Combined Coding and Modulation with decreased decoding Complexity", IEEE ISIT '88, Kobe, Japan, June 1988. They regarded the modulated signal as being the sum of two amplitude modulated signals in phase-quadrature and coded separately in the two dimensions. Thus the two-dimensional constellation was regarded as two one-dimensional constellations transmitted in quadrature. It follows that the set partitioning process discussed with reference to FIG. 1 is carried out in the two dimensions separately. This is shown in FIG. 2A for the x dimension. Note that the labels actually correspond to the x coordinate as measured from the leftmost point; if different senses are chosen for the 0/1 division at any partition this simply results in one or more bits of the label being inverted relative to the coordinate bit.
Coding is illustrated in FIG. 3 for the general case. Here the as and bs are elements of codes as before. Now each dimension has its own codeword array, producing labels L.sub.x1, . . . L.sub.xN ; L.sub.y1 . . . L.sub.yN. In principle different codes could be used in each dimension's array if quadrant phase immunity is not required.
FIG. 4 shows a specific example of such a scheme assuming we wish to send 3 bits/symbol over a 16-point QAM signal constellation, with a block size of N=8. We require two bits per symbol in each dimension (=four bits/symbol); for a block we generate 4N=32 bits from m=24 input bits (i.e. the rate of the code is 24/32=3/4). The 24 input bits are divided into two groups of 12 (note that these schemes take no cognizance of the meaning of the input bits and it is immaterial whether the 24 bits are eight 3-bit words or three 8-bit words; thus the division into two groups is arbitrary). Of each group of 12 bits, four are coded into the 8 bits of the first row of the relevant array using the (8, 4, 4) Reed-Muller code, and the remaining 8 pass unmodified into the second row. Assuming the FIG. 2A partioning, each column forms the x or y coordinate of a symbol to be transmitted.
Again, the top row forms the least significant bit.
A 16-point constellation is shown in FIG. 5 with labels derived from the FIG. 2A partioning. The method employed for decoding this array involves decoding separately in the two dimensions. Imagine that a demodulator has received the eight points (relative to the lower left point of the constellation) of a block and the x-coordinates of the received points are EQU (1.02, 2.94, 0.23, 2.53, 3.23, 0.45, 2.03, 1.24)
The first step is to regenerate the first row of the coding matrix; these bits indicate whether the coordinate is odd or even; thus the received vector is converted into a vector with values between 0 and 1 indicating the distance of the received x-coordinate from the nearest even number, viz EQU (0.98, 0.94, 0.23, 0.53, 1.0, 0.45, 0.03, 0.76)
Note that 3.23 is given the value 1.0 since the largest even coordinate in the constellation is 2.
Application of a soft-decision decoding algorithm gives information digits 1010, implying a transmitted top row codeword of 11001100. This type of soft-decision decoding is well known; however for a more detailed description in relation to decoding in the separate dimensions see R. G. C. Williams, "Low Complexity Block Coded Modulation", Ph.D. Thesis, Victoria University of Manchester, U.K., August 1988.
Knowing the least significant bit of each symbol (i.e. whether the symbol is even (0) or odd (1)) an inspection of the received coordinates shows that the transmitted vector is (1, 3, 0, 2, 3, 1, 2, 2) and the remaining eight information bits are (0, 1, 0, 1, 1, 0, 1, 1). Clearly if more than two rows were involved, then the algorithm could be applied progressively; in a more sophisticated system the results of later decisions could be fed back to modify earlier decisions (again discussed by Williams).
Note that if the same codes are chosen for each dimension's array then there are fewer different decoders required for the decoding since each array has only half the number of rows of the equivalent 2 dimensional array. Another feature of this scheme is that the decoders work with 1-dimensional distances and are therefore not as complex as the decoders used in the original scheme which worked with 2-dimensional distances due to the nature of the signal constellations.